package logic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

/**
 * @author Marco Gallardo Casu
 * @author Miguel Cisneros Rojas
 * 
 */
public class Tree {

	private Operation operator;
	private Operand operand;
	private Tree son1;
	private Tree son2;
	private Tree son3;
	private Tree father;
	private int minDepth;
	private int maxDepth;
	private int numNodes;
	private int depth;

	public Tree() {
		Random r = new Random();
		int minDepth = r.nextInt(2) + 1;
		int maxDepth = r.nextInt(8) + minDepth;
		Tree t = new Tree(minDepth, maxDepth, null);
		this.operator = t.operator;
		this.operand = t.operand;
		this.son1 = t.son1;
		this.son2 = t.son2;
		this.son3 = t.son3;
		this.father = t.father;
		this.minDepth = t.minDepth;
		this.maxDepth = t.maxDepth;
		this.numNodes = t.numNodes;
		this.depth = t.depth;
	}

	public Tree(int minDepth, int maxDepth, Operation operator,
			Operand operand, int numNodes, int depth, Tree father) {
		this.father = father;
		this.minDepth = minDepth;
		this.maxDepth = maxDepth;
		this.operand = operand;
		this.operator = operator;
		this.numNodes = numNodes;
		this.depth = depth;
	}

	public Tree(int minDepth, int maxDepth, Tree father) {
		this.father = father;
		this.minDepth = minDepth;
		this.maxDepth = maxDepth;
		if (minDepth >= 0 && minDepth <= maxDepth) {
			if (minDepth > 0) {
				genSubTree(minDepth, maxDepth);
			} else {
				genSubTree2(minDepth, maxDepth);
			}
		} else {
			genSubTree2(minDepth, maxDepth);
		}
	}

	public Tree clone() {
		Tree t = clone(father);
		t.setFather(father);
		return t;
	}

	public boolean evaluate(boolean[] a, boolean[] d) {
		boolean sol = false;
		if (operand != null) {
			switch (operand) {
			case A0:
				sol = a[0];
				break;
			case A1:
				sol = a[1];
				break;
			case D0:
				sol = d[0];
				break;
			case D1:
				sol = d[1];
				break;
			case D2:
				sol = d[2];
				break;
			default:
				sol = d[3];
				break;
			}
		} else {
			switch (operator) {
			case IF:
				sol = son1.evaluate(a, d) ? son2.evaluate(a, d) : son3
						.evaluate(a, d);
				break;
			case AND:
				sol = son1.evaluate(a, d) && son3.evaluate(a, d);
				break;
			case OR:
				sol = son1.evaluate(a, d) || son3.evaluate(a, d);
				break;
			default:
				sol = !son1.evaluate(a, d);
				break;
			}
		}

		return sol;
	}

	public int getNumNodes() {
		return numNodes;
	}

	public Operand getOperand() {
		return operand;
	}

	public Operation getOperator() {
		return operator;
	}

	public Tree getSon1() {
		return son1;
	}

	public Tree getSon2() {
		return son2;
	}

	public Tree getSon3() {
		return son3;
	}

	/**
	 * Mutate a node, if it's an operand, select a random operand, else a random
	 * operator.
	 */
	public void mutate(double p) {
		Random r = new Random();

		// BFS uses queue data structure
		LinkedList<Tree> list = new LinkedList<Tree>();
		list.add(this);
		Tree t1 = this;
		while (!list.isEmpty()) {
			t1 = list.remove();
			list.addAll(t1.getSons());
			if (r.nextDouble() < p) {
				if (t1.isLeaf()) {
					t1.setOperand(operandRandom());
				} else {
					Operation operator = operatorRandom();
					t1.setOperator(operator);
					int numSons = t1.getNumSons();
					if (operator == Operation.IF) {
						if (numSons == 1) {
							t1.setSon2(new Tree(minDepth, maxDepth, t1));
							t1.setSon3(new Tree(minDepth, maxDepth, t1));
						} else if (numSons == 2) {
							t1.setSon2(new Tree(minDepth, maxDepth, t1));
						}
					} else if (operator == Operation.NOT) {
						if (numSons > 1) {
							t1.setSon2(null);
							t1.setSon3(null);
						}
					} else {
						if (numSons > 2) {
							t1.setSon2(null);
						} else if (numSons < 2) {
							t1.setSon3(new Tree(minDepth, maxDepth, t1));
						}
					}
				}
			}
		}
	}

	/**
	 * Breadth-First Search
	 * 
	 * @param node
	 * @return
	 */
	public Tree searchNode(int node) {

		if (node == 0) {
			return this;
		}

		if (node < 0) {
			return null;
		}

		// BFS uses queue data structure
		LinkedList<Tree> list = new LinkedList<Tree>();
		list.add(this);
		Tree t = this;
		int cN = -1;
		while (cN != node && !list.isEmpty()) {
			t = list.remove();
			list.addAll(t.getSons());
			cN++;
		}
		list.clear();
		return cN == node ? t : null;

	}

	public void setDepths(int minDepth, int maxDepth) {
		setMinDepth(minDepth);
		setMaxDepth(maxDepth);
	}

	public void setOperand(Operand operand) {
		this.operand = operand;
	}

	public void setOperator(Operation operator) {
		this.operator = operator;
	}

	public void setSon1(Tree son1) {
		this.son1 = son1;
	}

	public void setSon2(Tree son2) {
		this.son2 = son2;
	}

	public void setSon3(Tree son3) {
		this.son3 = son3;
	}

	/**
	 * Sustitute a subTree with root "node" for "tree"
	 * 
	 * @param node
	 * @param tree
	 */
	public void sustitute(int node, Tree tree) {
		// BFS uses queue data structure
		LinkedList<Tree> list = new LinkedList<Tree>();
		list.add(this);
		Tree t = this;
		int cN = -1;
		while (cN != node && !list.isEmpty()) {
			t = list.remove();
			list.addAll(t.getSons());
			cN++;
		}
		list.clear();
		Tree father = t.getFather();
		if (father.son1 == t) {
			father.setSon1(tree);
		} else if (father.son3 == t) {
			father.setSon3(tree);
		} else {
			father.setSon2(tree);
		}
		tree.setFather(father);
	}

	@Override
	public String toString() {
		String s = " (";

		Tree t = this;
		if (t.isLeaf()) {
			s += t.getOperand();
		} else {
			s += t.getOperator();
			for (Tree son : t.getSons()) {
				if (son != null) {
					s += son.toString();
				}
			}
		}

		return s + ")";
	}

	public void update() {
		int[] att = update2();
		depth = att[0];
		numNodes = att[1];		
	}

	private Tree clone(Tree father) {
		if (operand != null) {
			return new Tree(minDepth, maxDepth, operator, operand, 1, 0, father);
		}

		Tree t = new Tree(minDepth, maxDepth, operator, operand, numNodes,
				depth, father);
		if (son1 != null) {
			t.setSon1(son1.clone(t));
		}
		if (son3 != null) {
			t.setSon3(son3.clone(t));
		}
		if (son2 != null) {
			t.setSon2(son2.clone(t));
		}
		return t;
	}

	private void genLeaf() {
		setOperand(operandRandom());
		setNumNodes(1);
		setDepth(0);
	}

	/**
	 * Generate a random subTree.
	 * 
	 * @param minDepth
	 * @param maxDepth
	 */
	private void genSubTree(int minDepth, int maxDepth) {
		this.operator = operatorRandom();

		// Left son
		son1 = new Tree(minDepth - 1, maxDepth - 1, this);
		setNumNodes(numNodes + son1.getNumNodes() + 1);
		setDepth(son1.getDepth() + 1);
		if (operator != Operation.NOT) {
			if (operator == Operation.IF) {
				// Center son
				son2 = new Tree(minDepth - 1, maxDepth - 1, this);
				setNumNodes(numNodes + son2.getNumNodes());
				setDepth(Math.max(depth, son2.getDepth() + 1));
			}
			// Right son
			son3 = new Tree(minDepth - 1, maxDepth - 1, this);
			setNumNodes(numNodes + son3.getNumNodes());
			setDepth(Math.max(depth, son3.getDepth() + 1));
		}
	}

	private void genSubTree2(int minDepth, int maxDepth) {
		if (maxDepth == 0) {
			genLeaf();
		} else {
			int type = new Random().nextInt(2);
			if (type == 1) {
				genSubTree(minDepth, maxDepth);
			} else {
				genLeaf();
			}
		}
	}

	private int getDepth() {
		return depth;
	}

	private Tree getFather() {
		return father;
	}

	private int getNumSons() {
		int sons = 0;
		if (son1 != null) {
			sons++;
			if (son3 != null) {
				sons++;
				if (son2 != null) {
					sons++;
				}
			}
		}
		return sons;
	}

	private ArrayList<Tree> getSons() {
		ArrayList<Tree> sons = new ArrayList<Tree>(3);

		if (!isLeaf()) {
			sons.add(son1);
			if (son3 != null) {
				if (son2 != null) {
					sons.add(son2);
				}
				sons.add(son3);
			}
		}

		return sons;
	}

	private boolean isLeaf() {
		return son1 == null;
	}

	private Operand operandRandom() {
		int i = new Random().nextInt(6);
		Operand operand;
		switch (i) {
		case 0:
			operand = Operand.A0;
			break;
		case 1:
			operand = Operand.A1;
			break;
		case 2:
			operand = Operand.D0;
			break;
		case 3:
			operand = Operand.D1;
			break;
		case 4:
			operand = Operand.D2;
			break;
		default:
			operand = Operand.D3;
			break;
		}
		return operand;
	}

	private Operation operatorRandom() {
		int i = new Random().nextInt(4);
		Operation operation;
		switch (i) {
		case 0:
			operation = Operation.IF;
			break;
		case 1:
			operation = Operation.AND;
			break;
		case 2:
			operation = Operation.OR;
			break;
		default:
			operation = Operation.NOT;
			break;
		}
		return operation;
	}

	private void setDepth(int depth) {
		this.depth = depth;
	}

	private void setFather(Tree father) {
		this.father = father;
	}

	private void setMaxDepth(int maxDepth) {
		this.maxDepth = maxDepth;
	}

	private void setMinDepth(int minDepth) {
		this.minDepth = minDepth;
	}

	private void setNumNodes(int numNodes) {
		this.numNodes = numNodes;
	}

	private int[] update2() {
		if (isLeaf()) {
			int[] sol = {0, 1};
			return sol;
		} else {
			int[] sol = new int[2];
			int[] aux = son1.update2();
			sol[0] = aux[0] + 1;
			sol[1] = aux[1] + 1;
			if (son3 != null) {
				aux = son3.update2();
				sol[0] = Math.max(sol[0], aux[0] + 1);
				sol[1] += aux[1];
				if (son2 != null) {
					aux = son2.update2();
					sol[0] = Math.max(sol[0], aux[0] + 1);
					sol[1] += aux[1];
				}
			}
			return sol;
		}
	}
}
